package com.leetcode.No0895;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @program: FreqStack
 * @description: 最大频率栈
 * @author: Wang Zhihua
 * @date: 2022-12-02
 */
public class FreqStack {

    // value -> List<Item(value, idx)>
    private Map<Integer, LinkedList<Item>> map;
    private Item endItem;
    private int size;
    private int maxNum;

    public FreqStack() {
        map = new HashMap<>();
        size = 0;
        maxNum = 0;
    }

    public void push(int val) {
        Item item = new Item(val, ++size);
        if (endItem == null) {
            endItem = item;
        } else {
            endItem.next = item;
            item.pre = endItem;
            endItem = item;
        }
        LinkedList<Item> itemList = map.getOrDefault(val, new LinkedList<>());
        itemList.add(item);
        map.put(val, itemList);
        maxNum = Math.max(maxNum, itemList.size());
    }

    public int pop() {
        int maxIdx = -1;
        Item targetItem = new Item(-1, -1);
        int targetNum = 0;
        for (LinkedList<Item> itemList : map.values()) {
            if (itemList.size() == maxNum) {
                Item last = itemList.getLast();
                if (maxIdx < last.idx) {
                    maxIdx = last.idx;
                    targetItem = last;
                }
                ++targetNum;
            }
        }

        if (targetNum == 1) {
            --maxNum;
        }

        Item pre = targetItem.pre;
        Item next = targetItem.next;
        if (pre != null) {
            pre.next = next;
        }
        if (next != null) {
            next.pre = pre;
        }

        map.get(targetItem.value).pollLast();

        return targetItem.value;
    }

    private class Item {
        Item pre;
        Item next;
        int value;
        int idx;
        Item(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }
    }

    @Test
    public void test01() {
        FreqStack freqStack = new FreqStack();
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }

    @Test
    public void test02() {
        FreqStack freqStack = new FreqStack();
        freqStack.push(4);
        freqStack.push(0);
        freqStack.push(9);
        freqStack.push(3);
        freqStack.push(4);
        freqStack.push(2);
        System.out.println(freqStack.pop());
        freqStack.push(6);
        System.out.println(freqStack.pop());
        freqStack.push(1);
        System.out.println(freqStack.pop());
        freqStack.push(1);
        System.out.println(freqStack.pop());
        freqStack.push(4);
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }

}
